package pack3.utils;

public class Heap {
    private int []arr;
    private int size;

    //将一个数组调整为堆结构(大根堆)
    public static void createHeap_1(int []arr){//向上
        for (int i = 0; i < arr.length; i++) {
            jugeUp(arr,i);
        }
    }

    public static void createHeap_2(int []arr){//向下
        int end=(arr.length-1-1)/2;
        while(end>=0){
            jugeDown(arr,end, arr.length);
            end--;
        }
    }

    //向上调整(插入元素)
    public static void jugeUp(int[]arr,int childIndex){
        int child=childIndex;
        int parent=(childIndex-1)/2;
        while(child>=0){
            if(arr[child]>arr[parent]){
                Utils.swap(arr,child,parent);
                child=parent;
                parent=(parent-1)/2;
            }else{
                break;
            }
        }
    }

    public static void jugeDown(int[]arr,int parentIndex,int length){
        int parent=parentIndex;
        int child=parent*2+1;
        while(child<length){
            if((child+1)<length&&arr[child]<arr[child+1]){
                child++;
            }
            if(arr[parent]<arr[child]){
                Utils.swap(arr,parent,child);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }


    public Heap(int maxSize) {
        this.arr = new int[maxSize];
        this.size=0;
    }
}
